package algotithm.weekendrace.leetcode225.test4;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/24-10:09
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 4;
        int boxes = solution.minimumBoxes(n);
        System.out.println(boxes);
    }

    public int minimumBoxes(int n) {
        int cur = 0, add = 2, level = 1;
        while (cur < n) {
            cur += level;
            level += add;
            add += 1;
        }
        add -= 1;
        level -= add;
        if (cur == n) {
            return level;
        } else {
            cur -= level;
            add -= 1;
            level -= add;
            int needMore = (int)((Math.sqrt(1 + 8L * (n - cur)) - 1) / 2);
            while (cur + sumEqual(needMore) < n) {
                needMore += 1;
            }
            return needMore + level;
        }
    }

    private int sumEqual(int n) {
        return (1 + n) * n / 2;
    }

}
